﻿using System;
using System.Collections.Generic;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.Utils;

namespace Algoritmia.DataStructures.Trees
{
    public class DigraphTree<T> : IRootedTree<T>
    {
        private readonly IEditableDigraph<T> _graph;
        private readonly T _root;

        public DigraphTree(IEditableDigraph<T> graph , T root)
        {
            _graph = graph;
            _root = root;
        }

        #region IRootedTree<T> Members

        public T Root
        {
            get { return _root; }
        }

        public IEnumerable<T> Successors(T node)
        {
            return _graph.Successors(node);
        }

        public IEnumerable<T> Predecessors(T node)
        {
            return _graph.Predecessors(node);
        }

        public int InDegree(T node)
        {
            return _graph.InDegree(node);
        }

        public int OutDegree(T node)
        {
            return _graph.OutDegree(node);
        }

        public IEnumerable<IRootedTree<T>> SubTrees()
        {
            foreach(var successor in _graph.Successors(_root))
            {
                yield return Tree(successor);
            }
        }

        public IRootedTree<T> Tree(T root)
        {
            var edges = new List<Tuple<T, T>>();
            FillTree(root,edges);
            return new DigraphTree<T>(new Digraph<T>(edges: edges), root);
        }

        #endregion

        private void FillTree(T parent, List<Tuple<T,T>> edges)
        {
            foreach(var successor in Successors(parent))
            {
                edges.Add(new Tuple<T, T>(parent,successor));
                FillTree(successor,edges);
            }
        }

        public override string ToString()
        {
            return String.Format("{0} <{1}> root = {2} graph = {3}", GetType().Name, typeof(T).Name, _root, _graph);
        }
    }
}
